/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lk;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Date;
import java.util.Scanner;
import java.lang.Math;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Random;

/**
 *
 * @author apple
 */
public class LinKernighan {
    ArrayList<Pais> arPais;
    ArrayList<Paquete> arPaquete;
    ArrayList<Almacen> arAlmacen;
    ArrayList<Vuelo> arVuelo;
    ArrayList<VueloXRuta> arVueloXRuta = new ArrayList<VueloXRuta>(); //ver si es necesario
    ArrayList<ReservaAlmacen> arReserva;
    Ruta ruta;
    int  opt;
    
    // TODO LOGIC HERE
    public LinKernighan(){
        arPais = new ArrayList<Pais>();
        arPaquete = new ArrayList<Paquete>();
        arAlmacen = new ArrayList<Almacen>();
        arVuelo = new ArrayList<Vuelo>();
        arVueloXRuta = new ArrayList<VueloXRuta>();
    }

    public void readData() throws FileNotFoundException{
        Scanner sc = new Scanner( new File( "input.in" ) ) ;
        int n;
        arPais = new ArrayList<Pais>() ;
        n = sc.nextInt() ;
        for(int i = 0 ; i < n ; i++){
            int x = sc.nextInt() ;
            int y = sc.nextInt() ;
            String nombrePais = sc.next();
            String nombreCiudad = sc.next();
            arPais.add( new Pais( i, x , y , nombrePais , nombreCiudad ) ) ;
        }

        arPaquete = new ArrayList<Paquete>() ;
        n = sc.nextInt() ;
        for(int i = 0 ; i < n ; i++){
            int estado = sc.nextInt() ;
            int precio = sc.nextInt() ;
            int anho = sc.nextInt();
            int mes = sc.nextInt();
            int dia = sc.nextInt();
            int hora = sc.nextInt();
            
            arPaquete.add( new Paquete( i, estado, precio ) ) ;
        }


        
        arVuelo = new ArrayList<Vuelo>() ;
        int m = sc.nextInt() ;
        for(int i = 0 ; i < m ; i++){
            int ini = sc.nextInt() ;
            int fin = sc.nextInt() ;
            int cap = sc.nextInt() ;
            int dur = sc.nextInt() ;
            double costo = sc.nextDouble() ;
            //arVuelos.add( new Vuelo( arCity.get( ini ) , arCity.get( fin ) , cap , dur , costo ) ) ;
//            arVuelos.get( i ).write() ;
        }
        /*
        ArrayList<Integer> R = new ArrayList<Integer>() ;
        R.add( sc.nextInt() ) ;
        R.add( sc.nextInt() ) ;
        
        //init() ;
        return R ;
         */
    }

    /*PARA EL GRASP **************/
    public int calcularMaxIt(){
        return 5;
    }
    
    public int funObj(ArrayList<Vuelo> a){
        int recorrido = 0;
        for(int i = 0; i < a.size(); i++){
            recorrido += a.get(i).recorrido;
        }
        return recorrido;
    }

    public ArrayList<Vuelo> getCandidatos(Almacen a, Fecha fechaRegistro, int continental){
        ArrayList<Vuelo> resp = new ArrayList<Vuelo>();

        if (continental == 0)
            for(int i = 0; i < arVuelo.size(); i++){
                if(arVuelo.get(i).origen == a && fechaRegistro.esMenorQue(arVuelo.get(i).fechaSalida) && arVuelo.get(i).fechaLlegada.esMenorQue(fechaRegistro.mas1o2Dias(1))/*FALTA PONER LÍMITE DE TIEMPO Y MAYOR Q TIEMPO ACTUAL*/)
                resp.add(arVuelo.get(i));
            }
        else if (continental == 1)
            for(int i = 0; i < arVuelo.size(); i++){
                if(arVuelo.get(i).origen == a && fechaRegistro.esMenorQue(arVuelo.get(i).fechaSalida) && arVuelo.get(i).fechaLlegada.esMenorQue(fechaRegistro.mas1o2Dias(2))/*FALTA PONER LÍMITE DE TIEMPO Y MAYOR Q TIEMPO ACTUAL*/)
                resp.add(arVuelo.get(i));
            }


        return resp;
    }

    public ArrayList<Vuelo> ordenarCandidatos(ArrayList<Vuelo> arrV){

        return arrV;
    }
    public ArrayList<Vuelo> cortarCandidatos(double alpha, ArrayList<Vuelo> arrV){

        return arrV;
    }

    /****************************/
    
    public Ruta generarRutaGrasp(Almacen origen, Almacen destino, Fecha fechaCreacion){

        int continental;
        if(origen.pais.continente == destino.pais.continente)
            continental = 0;
        else
            continental = 1;


        double alpha = 0.45;
        int max_iteraciones = calcularMaxIt();
        ArrayList<Vuelo> solucionBest = new ArrayList<Vuelo>();

        for(int i = 0; i < max_iteraciones; i++){            
            ArrayList<Vuelo> solucion = new ArrayList<Vuelo>();
            ArrayList<Vuelo> usados = new ArrayList<Vuelo>();
            while(solucion.isEmpty() || solucion.get(solucion.size() - 1).destino.diff(destino) ){
                ArrayList<Vuelo> candidatos = new ArrayList<Vuelo>();
                if (solucion.isEmpty())
                    candidatos = getCandidatos(origen, fechaCreacion, continental);
                else
                    candidatos = getCandidatos(solucion.get(solucion.size() - 1).destino, fechaCreacion, continental);
                ordenarCandidatos(candidatos);
                cortarCandidatos(alpha, candidatos);


                int aleatorio = new Double(Math.random() * candidatos.size()).intValue();
                while(usados.contains(candidatos.get(aleatorio))){
                    aleatorio = new Double(Math.random() * candidatos.size()).intValue();
                }
                //Random rand = new Random();
                //int aleatorio = rand.nextInt(candidatos.size());
                solucion.add(candidatos.get(aleatorio));
                usados.add(candidatos.get(aleatorio));
            }

            if(solucionBest.isEmpty() || (funObj(solucion) < funObj(solucionBest)))
                solucionBest = solucion;
        }

        Ruta rutaG = new Ruta(origen, destino);
        for(int i = 0; i < solucionBest.size() - 1; i++){
            arVueloXRuta.add(new VueloXRuta(rutaG, solucionBest.get(i)));

            if(i == 0)
                //arReserva.add(new ReservaAlmacen(origen, new Paquete(), fechaCreacion, solucionBest.get(i).fechaSalida, new Fecha(), new Fecha(), 0));
                arReserva.add(new ReservaAlmacen(origen, null, fechaCreacion, solucionBest.get(i).fechaSalida, null, null, 0));
            if(i == solucionBest.size() - 1){
                if(continental == 0)
                    arReserva.add(new ReservaAlmacen(solucionBest.get(solucionBest.size() - 1).origen, null, solucionBest.get(solucionBest.size() - 1).fechaSalida, fechaCreacion.mas1o2Dias(1), null, null, 0));
                else if(continental == 1)
                    arReserva.add(new ReservaAlmacen(solucionBest.get(solucionBest.size() - 1).origen, null, solucionBest.get(solucionBest.size() - 1).fechaSalida, fechaCreacion.mas1o2Dias(2), null, null, 0));
            }
            else{
                arReserva.add(new ReservaAlmacen(solucionBest.get(i-1).destino, null, solucionBest.get(i-1).fechaLlegada, solucionBest.get(i).fechaSalida, null, null, 0));
            }

        }
        return rutaG;
    }
    
    public Ruta LK(Almacen origen, Almacen destino, Fecha fechaCreacion) {
        int cantidad; 
        opt = 2;
        ArrayList<Vuelo> vueloX;
        ArrayList<Vuelo> vueloY;
        ArrayList<ArrayList<Vuelo>>vuelosY;
        VueloXRuta vueloxruta = new VueloXRuta();
        
        ruta = generarRutaGrasp(origen, destino, fechaCreacion);
        
        while (opt < vueloxruta.Cantidad(ruta)){
            cantidad = vueloxruta.Cantidad(ruta);
            for (int i=0; i < cantidad ; i++){
                vueloX = vueloxruta.get(ruta,i, opt); 
                /*debe coger opt vuelos continuos*/
                vuelosY = vueloxruta.getRandom(arVuelo, vueloX, opt, fechaCreacion, arReserva); 
                /*porque me tiene que 
                *coger cualquier vuelo menos los que estan en la ruta
                *puede coger 1 <= a <= opt vuelos para reemplazar X  
                * origen, destino x =  origen, destino y (sin importar cantidad de items en array)
                */
                vueloY = ruta.evaluarF(i, opt, vueloX, vuelosY);
                if (!vueloY.isEmpty()){/*f = función objetivo*/
                   ruta = vueloxruta.Reemplazar(ruta, vueloX, vueloY);
                   break; 
                   /*porque si reemplaza un vuelo tiene que volver a evaluar la ruta*/
                }
                /*else evaluar el sgte vuelo*/
                /*evaluar incremento opt*/
                if ( i == (vueloxruta.Cantidad(ruta) -1)) opt++;
            }
       }
       return ruta; 
   }

    public void imprimirResultado(Ruta rutaPaquete, Paquete paquete){
        System.out.println("El paquete " + paquete.idPaquete + " paso por la ruta " + rutaPaquete.idRuta);
        System.out.println("Se registro en la fecha " + paquete.fechaCreacion.aString() + ", saló en la fecha " + rutaPaquete.fechaSalida.aString() + " y llegó en la fecha " + rutaPaquete.fechaLlegada.aString());
    }

    public void start() throws FileNotFoundException{
        readData();
        for (int i = 0; i < arPaquete.size(); i++){
            Ruta rutaPaquete = new Ruta();
            rutaPaquete = LK(arPaquete.get(i).origen, arPaquete.get(i).destino, arPaquete.get(i).fechaCreacion);
            imprimirResultado(rutaPaquete, arPaquete.get(i));
        }


    }
}
